/*--------------------------------------------------------------------

       +---------------------------------------------------+
       |                                                   |
       |     C H O M S K Y     N O R M A L     F O R M     |
       |                                                   |
       +---------------------------------------------------+

         This program finds out the equivalent CHOMSKY NORMAL
   FORM of a given Grammar.

         The statement of CHOMSKY NORMAL FROM is as follows :

         Any context-free language without $ (epsilon) is generated
   by a grammar in which all productions are of the form A -> BC or
   A -> a. Here, A , B and C, are variables and  a  is a terminal.

--------------------------------------------------------------------*/

 # include <stdio.h>
 # include <dir.h>

 struct prod {
               char sym , production[10] ;
              } ;

 struct var {
              char name[5] ;
             } ;

 struct arr {
              char elt , map[5] , string[10] ;
             } ;

 struct file {
               char fname[15] ;
              } ;

 struct prod prodn[20] ;
 struct var vars[20] , terms[20] ;
 struct arr map[20] ;
 struct ffblk fil ;
 struct file files[11] ;
 int prodns = 0 , no_vars = 0 , no_terms = 0 , start = 128 , derived = 0 ;

 # include <pop.c>

 int read_file (char fname[])
  {
    FILE *fp ;
    char string[80] , temp[5] ;
    int i , j ;

    if (( fp = fopen (fname,"r")) == NULL )
      return (-1) ;
    fgets (string,80,fp) ;
    while ( !feof(fp) )
     {
       for ( i = 0 ; string[i] == ' ' ; i++ ) ;
       switch ( string[i] )
        {
          case 'V' : for ( ; string[i] != '{' ; i++ ) ;
                     i++ ;
                     for ( ; string[i] != '}' ; )
                      {
                        if ( string[i] == ',' )
                          i++ ;
                        for ( j = 0 ; (string[i] != '}') && (string[i] != ',') ; j++ , i++ )
                          vars[no_vars].name[j] = string[i] ;
                        vars[no_vars++].name[j] = '\0' ;
                       }
                     break ;
          case 'T' : for ( ; string[i] != '{' ; i++ ) ;
                     i++ ;
                     for ( ; string[i] != '}' ; )
                      {
                        if ( string[i] == ',' )
                          i++ ;
                        for ( j = 0 ; (string[i] != '}') && (string[i] != ',') ; j++ , i++ )
                          terms[no_terms].name[j] = string[i] ;
                        terms[no_terms++].name[j] = '\0' ;
                       }
                     break ;
          case '-' : i++ ;
                     for ( ; string[i] == ' ' ; i++ ) ;
                     prodn[prodns].sym = string[i] ;
                     for ( ; string[i] != '>' ; i++ ) ;
                     i++ ;
                     for ( ; string[i] == ' ' ; i++ ) ;
                     for ( ; string[i] != '.' ; )
                      {
                        if ( string[i] == '|' )
                         {
                           i++ ;
                           prodn[prodns].sym = prodn[prodns-1].sym ;
                          }
                        for ( j = 0 ; ( string[i] != '.' ) && (string[i] != '|') ; j++ , i++ )
                          prodn[prodns].production[j] = string[i] ;
                        prodn[prodns++].production[j] = '\0' ;
                       }
                     break ;
          default  : break ;
         }
       fgets (string,80,fp) ;
      }
   }

 int find_epsilon_productions ()
  {
    int i , j ;

    /* Find epsilon in the productions if present */
    for ( i = 0 ; i < prodns ; i++ )
      for ( j = 0 ; prodn[i].production[j] ; j++ )
        if ( prodn[i].production[j] == '$' )
         {
           clear_rect_a (1,1,25,80,15) ;
           printf ("\n\n                    INVALID PRODUCTION FOUND !") ;
           printf ("\n\n          A Production has $ in it.\n          ") ;
           printf ("Hence the given set of productions cannot be converted.") ;
           printf ("\n\n Production is =>  %c -> %s",prodn[i].sym,prodn[i].production) ;
           getch () ;
           return (-1) ;
          }
    return (0) ;
   }

 int find_terminal (char term)
  {
    int i ;

    for ( i = 0 ; i < prodns ; i++ )
      if ( map[i].string[0] == term )
        return (i) ;
    return (-1) ;
   }

 substitute_terminals ()
  {
    int i , index ;
    char temp[5] ;

    for ( i = 0 ; i < prodns ; i++ )
     {
       if ( strlen (prodn[i].production) > 1 )
        {
          index = find_terminal (prodn[i].production[0]) ;
          if ( index == -1 )
           {
             map[derived].elt = start ;
             strcpy (map[derived].map,"C") ;
             itoa (derived,temp,10) ;
             strcat (map[derived].map,temp) ;
             map[derived].string[0] = prodn[i].production[0] ;
             map[derived].string[1] = '\0' ;
             prodn[i].production[0] = start ;
             derived++ ;
             start++ ;
            }
          else
             prodn[i].production[0] = map[index].elt ;
         }
      }
   }

 int find_variable (char *var)
  {
    int i ;

    for ( i = 0 ; i < prodns ; i++ )
      if ( strcmp (map[i].string,var) == 0 )
        return (i) ;
    return (-1) ;
   }

 substitute_remaining ()
  {
    int i , j , index ;
    char temp[5] , temp1[10] ;

    for ( i = 0 ; i < prodns ; i++ )
     {
       if ( strlen (prodn[i].production) > 1 )
        {
          for ( j = 1 ; prodn[i].production[j] ; j++ )
            temp1[j-1] = prodn[i].production[j] ;
          temp1[j-1] = '\0' ;
          if ( strlen (temp1) > 1 )
           {
             index = find_variable (temp1) ;
             if ( index == -1 )
              {
                map[derived].elt = start ;
                strcpy (map[derived].map,"C") ;
                itoa (derived,temp,10) ;
                strcat (map[derived].map,temp) ;
                strcpy (map[derived].string,temp1) ;
                prodn[i].production[1] = start ;
                prodn[i].production[2] = '\0' ;
                derived++ ;
                start++ ;
               }
            }
         }
      }
   }

 substitute_derived ()
  {
    int i , j , index ;
    char temp[5] , temp1[10] ;

    for ( i = 0 ; i < derived ; i++ )
     {
       if ( strlen (map[i].string) > 2 )
        {
          if ( check_terminal (map[i].string[0]) == 1 )
           {
             index = find_terminal (map[i].string[0]) ;
             if ( index == -1 )
              {
                map[derived].elt = start ;
                strcpy (map[derived].map,"C") ;
                itoa (derived,temp,10) ;
                strcat (map[derived].map,temp) ;
                map[derived].string[0] = map[i].string[0] ;
                map[derived].string[1] = '\0' ;
                derived++ ;
                start++ ;
               }
             else
               map[i].string[0] = map[index].elt ;
            }

          for ( j = 1 ; map[i].string[j] ; j++ )
            temp1[j-1] = map[i].string[j] ;
          temp1[j-1] = '\0' ;
          if ( strlen (temp1) > 1 )
           {
             index = find_variable (temp1) ;
             if ( index == -1 )
              {
                map[derived].elt = start ;
                strcpy (map[derived].map,"C") ;
                itoa (derived,temp,10) ;
                strcat (map[derived].map,temp) ;
                strcpy (map[derived].string,temp1) ;
                map[i].string[1] = start ;
                map[i].string[2] = '\0' ;
                derived++ ;
                start++ ;
               }
            }
         }
      }
   }

 display ()
  {
    int i ;

    for ( i = 0 ; i < prodns ; i++ )
     {
       printf ("\n               %c -> ",prodn[i].sym) ;
       printf ("%s",prodn[i].production) ;
      }
   }

 check_terminal (char term)
  {
    int i ;

    for ( i = 0 ; i < no_terms ; i++ )
      if ( terms[i].name[0] == term )
        return (1) ;

    return (-1) ;
   }

 display_value (char term,int val)
  {
    int i , found = 0 ;

    if ( val == 0 )
     {
       for ( i = 0 ; ( i < derived ) && ( found == 0 ) ; i++ )
        {
          if ( term == map[i].string[0] )
            found = 1 ;
         }
      }

    if ( val == 1 )
     {
       for ( i = 0 ; ( i < derived ) && ( found == 0 ) ; i++ )
        {
          if ( term == map[i].elt )
            found = 1 ;
         }
      }

    if ( found == 1 )
     {
       i-- ;
       printf ("%s ",map[i].map) ;
      }
   }

 display_derived ()
  {
    int i , j ;
    unsigned char c , c1 ;

    for ( i = 0 ; i < derived ; i++ )
     {
       printf ("\n               %s -> ",map[i].map) ;
       if ( strlen (map[i].string) == 1 )
         printf ("%s ",map[i].string) ;
       else
        {
          c1 = map[i].string[0] ;
          if ( ( strlen (map[i].string) == 2 ) && ( c1 > 127 ) )
           {
             for ( j = 0 ; j < derived ; j++ )
               if ( map[j].elt == c1 )
                {
                  printf ("%s ",map[j].map) ;
                  break ;
                 }
            }
          c = map[i].string[1] ;
          if ( ( strlen (map[i].string) == 2 ) && ( c > 127 ) )
           {
             if ( c1 < 127 )
               printf ("%c ",map[i].string[0]) ;
             display_value (map[i].string[1],1) ;
            }
          else
           {
             for ( j = 0 ; map[i].string[j] ; j++ )
              {
                if ( check_terminal (map[i].string[j]) == -1 )
                  printf ("%c ",map[i].string[j]) ;
                else
                  display_value (map[i].string[j],0) ;
               }
            }
         }
      }
   }

 display_mapped_productions ()
  {
    int i , j , found ;

    for ( i = 0 ; i < prodns ; i++ )
     {
       found = 0 ;
       printf ("\n               %c -> ",prodn[i].sym) ;
       if ( strlen (prodn[i].production) == 1 )
         printf ("%s ",prodn[i].production) ;
       else
        {
          for ( j = 0 ; ( j < derived ) && ( found == 0 ) ; j++ )
            if ( prodn[i].production[0] == map[j].elt )
              found = 1 ;
          if ( found == 1 )
           {
             j-- ;
             printf ("%s ",map[j].map) ;
            }

          for ( found = 0 , j = 0 ; ( j < derived ) && ( found == 0 ) ; j++ )
            if ( prodn[i].production[1] == map[j].elt )
              found = 1 ;
          if ( found == 1 )
           {
             j-- ;
             printf ("%s ",map[j].map) ;
            }
          else
           {
             printf ("%c ",prodn[i].production[1]) ;
            }
         }
      }

    display_derived () ;

    printf ("\n") ;
   }

 main (int argc,char *argv[])
  {
    char str[15] ;
    int i , flines = 0 , BACK = 32 ;

    if ( ( argc == 2 ) && ( strcmp (argv[1],"/C") == 0 ) )
      BACK = 23 ;

    clear_rect_a (1,1,25,80,BACK) ;
    dbox (1,1,24,79) ;

    cattrib_rect (2,25,4,30,15) ;
    dbox (2,25,4,30) ;
    i_shadow2 (2,25,4,30,7) ;
    pstr_a (3,30,"CHOMSKY  NORMAL FORM",15) ;
    pcpy (5,31) ;

    if ( argc == 1 )
      i = findfirst ("*.CNF",&fil,32) ;
    if ( ( argc == 2 ) && ( strcmp (argv[1],"/C") ) == 0 )
      i = findfirst ("*.CNF",&fil,32) ;
    if ( ( argc == 2 ) && ( strcmp (argv[1],"/C") ) != 0 )
      i = findfirst (argv[1],&fil,32) ;
    if ( argc == 3 )
      i = findfirst (argv[1],&fil,32) ;
    while ( ( i == 0 ) && ( flines < 10 ) )
     {
       strcpy (files[flines++].fname,fil.ff_name) ;
       i = findnext (&fil) ;
      }

    if ( flines == 0 )
     {
       cattrib_rect (10,30,2,17,BACK) ;
       dbox (10,30,2,17) ;
       i_shadow2 (10,30,2,17,7) ;
       pstr_a (11,31,"No Entries Found",15) ;
       getch () ;
       clear_rect_a (1,1,25,80,15) ;
       return ;
      }

    cattrib_rect (10,30,flines+1,15,BACK) ;
    dbox (10,30,flines+1,15) ;
    i_shadow2 (10,30,flines+1,15,7) ;
    i = popup (11,31,flines,BACK) ;

    strcpy (str,files[i].fname) ;

    i = read_file (str) ;
    if ( i == -1 )
     {
       clear_rect_a (1,1,25,80,15) ;
       return ;
      }

    if ( find_epsilon_productions () == -1 )
      return ;

    clear_rect_a (1,1,25,80,15) ;

    printf ("     The Original Productions are as follows :\n") ;

    display () ;

    printf ("\n\n                         Press Any Key To Continue " ) ;
    textattr (0x8F) ;
    cprintf ("...") ;
    getch () ;
    textattr (15) ;
    clrscr () ;

    substitute_terminals () ;

    substitute_remaining () ;

    substitute_derived () ;

    printf ("     The Productions in CHOMSKY NORMAL FORM are as follows :\n") ;

    /*for ( i = 0 ; i < derived ; i++ )
      printf ("\n*%c-%s-%s",map[i].elt,map[i].map,map[i].string) ;*/

    display_mapped_productions () ;

    getch () ;
   }
